import sys
from collections import defaultdict

grammar = {
    'P': ['L'],
    'L': ['S L\''],
    'L\'': ['; S L\'', 'ε'],
    'S': ['A', 'C'],
    'A': ['V = E', 'B'],
    'C': ['if ( B ) L else L'],
    'E': ['T E\''],
    'E\'': ['+ T E\'', 'ε'],
    'T': ['F T\''],
    'T\'': ['* F T\'', 'ε'],
    'F': ['( E )', 'id'],
    'B': ['U B\''],
    'B\'': ['and U B\'', 'ε'],
    'U': ['V U\''],
    'U\'': ['not V', 'ε'],
    'V': ['true', 'false', 'id']
}

ll1_table = {
    'P': {'id': 'L', 'if': 'L', 'true': 'L', 'false': 'L'},
    'L': {'id': 'S L\'', 'if': 'S L\'', 'true': 'S L\'', 'false': 'S L\''},
    'L\'': {';': '; S L\'', '$': 'ε'},
    'S': {'id': 'A', 'if': 'C', 'true': 'A', 'false': 'A'},
    'A': {'id': 'V = E', 'true': 'B', 'false': 'B'},
    'C': {'if': 'if ( B ) L else L'},
    'E': {'id': 'T E\'', '(': 'T E\''},
    'E\'': {'+': '+ T E\'', ')': 'ε', ';': 'ε', '$': 'ε', 'else': 'ε'},
    'T': {'id': 'F T\'', '(': 'F T\''},
    'T\'': {'*': '* F T\'', '+': 'ε', ')': 'ε', ';': 'ε', '$': 'ε', 'else': 'ε'},
    'F': {'id': 'id', '(': '( E )'},
    'B': {'id': 'U B\'', 'true': 'U B\'', 'false': 'U B\''},
    'B\'': {'and': 'and U B\'', ')': 'ε', ';': 'ε', '$': 'ε', 'else': 'ε'},
    'U': {'id': 'V U\'', 'true': 'V U\'', 'false': 'V U\''},
    'U\'': {'not': 'not V', ')': 'ε', 'and': 'ε', ';': 'ε', '$': 'ε', 'else': 'ε'},
    'V': {'id': 'id', 'true': 'true', 'false': 'false'}
}

def tokenize(s):
    return s.split() + ['$']



class SyntaxTreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []

    def add_child(self, node):
        self.children.append(node)

    def __repr__(self):
        return f"{self.value}"


class LL1Parser:
    def __init__(self, grammar, table, start='P'):
        self.grammar = grammar
        self.table = table
        self.start_symbol = start
        self.stack = ['#', start]
    
    def parse(self, tokens):
        input_index = 0
        steps = []
        
        # 语法树相关
        tree_stack = []  # 存储当前构建的子树根节点
        syntax_tree = SyntaxTreeNode(self.start_symbol)
        tree_stack.append(syntax_tree)

        while len(self.stack) > 1 or input_index < len(tokens):
            top = self.stack[-1]
            current_input = tokens[input_index]

            if top == '#':
                break

            if top in self.table and current_input in self.table[top]:
                production = self.table[top][current_input]
                steps.append(f"替换 {top} → {production}")
                self.stack.pop()

                # 获取当前语法树节点
                current_node = tree_stack[-1]
                current_node.value += f" → {production}"

                # 如果是空产生式
                if production == 'ε':
                    epsilon_node = SyntaxTreeNode('ε')
                    current_node.add_child(epsilon_node)
                    tree_stack.pop()
                    continue

                # 否则拆分产生式符号，从右到左入栈，并创建子节点
                symbols = production.split()
                new_children = []

                for symbol in reversed(symbols):
                    self.stack.append(symbol)
                    new_child = SyntaxTreeNode(symbol)
                    new_children.append(new_child)

                # 反转顺序（因为是从右往左压栈）
                current_node.children = new_children[::-1]

                # 将新产生的所有节点压入 tree_stack
                tree_stack = tree_stack[:-1]  # 弹出当前节点
                tree_stack.extend(new_children)

            elif top == current_input:
                steps.append(f"匹配 {current_input}")
                self.stack.pop()
                input_index += 1

                # 终结符直接作为叶子节点添加
                leaf = SyntaxTreeNode(current_input)
                tree_stack[-1].add_child(leaf)

            else:
                print("错误：无法匹配符号", top, "与输入", current_input)
                return False, None

        success = input_index == len(tokens) - 1 and self.stack == ['#']
        return success, syntax_tree
    

def print_syntax_tree(node, indent=""):
    print(indent + node.value)
    for child in node.children:
        print_syntax_tree(child, indent + "  ")


if __name__ == "__main__":
    parser = LL1Parser(grammar, ll1_table)

    # 示例输入字符串
    input_str = "id = id + id"
    tokens = tokenize(input_str)

    print("开始解析：", input_str)
    success, syntax_tree = parser.parse(tokens)

    if success:
        print("\n✅ 解析成功！")
        print("\n生成的语法树：")
        print_syntax_tree(syntax_tree)
    else:
        print("❌ 解析失败！")

